package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.Node;
import com.tgy.leetcode.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: tgy
 * @Date: 2/5/21 11:25 AM
 */
public class _07_找到二叉树中符合搜索二叉树条件的最大拓扑结构_nlogn {


    private static class NodeSubNum{

        int leftNum;
        int rightNum;


    }


    /**
     * 从每一个节点开始作为搜索二叉树向下查找节点，
     * @param root
     * @return
     */
    public static int findMaxSearchTree(TreeNode root) {

        if (root == null) {

            return 0;
        }


        Map<TreeNode,NodeSubNum> map = new HashMap<>();
        return findNum(root,map);
    }

    private static int findNum(TreeNode node, Map<TreeNode,NodeSubNum> map) {

        if (node == null) {

            return 0;
        }

        if (node.left == null && node.right == null) {

            map.put(node,new NodeSubNum());
            return 1;
        }

        int leftNum = findNum(node.left,map);
        int rightNum = findNum(node.right,map);

        NodeSubNum leftNodeSubNum = map.get(node.left);
        NodeSubNum rightNodeSubNum = map.get(node.right);
        NodeSubNum res = new NodeSubNum();


        if (leftNodeSubNum != null) {

            res.leftNum = leftNodeSubNum.leftNum + leftNodeSubNum.rightNum + 1 - findLeftSubCount(node,node.left,map);
        }

        if (rightNodeSubNum != null) {

            res.rightNum = rightNodeSubNum.leftNum + rightNodeSubNum.rightNum + 1 - findRightSubCount(node,node.right,map);
        }

        map.put(node,res);
        return Math.max(res.leftNum + res.rightNum + 1,Math.max(leftNum,rightNum));
    }

    private static int findLeftSubCount(TreeNode rootNode,TreeNode leftNode, Map<TreeNode,NodeSubNum> map) {

        TreeNode node = leftNode;

        while (node != null) {

            if (rootNode.val <= node.val) {

                NodeSubNum nodeSubNum = map.get(node);
                return nodeSubNum.leftNum + nodeSubNum.rightNum + 1;
            }

            node = node.right;
        }

        return 0;
    }

    private static int findRightSubCount(TreeNode rootNode, TreeNode rightNode, Map<TreeNode,NodeSubNum> map) {

        TreeNode node = rightNode;

        while (node != null) {

            if (rootNode.val >= node.val) {

                NodeSubNum nodeSubNum = map.get(node);
                return nodeSubNum.leftNum + nodeSubNum.rightNum + 1;
            }

            node = node.left;
        }

        return 0;
    }


    public static void main(String[] args) {

        TreeNode root = new TreeNode(6);

        root.left = new TreeNode(1);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(3);

        root.right = new TreeNode(12);
        root.right.left = new TreeNode(10);
        root.right.left.left = new TreeNode(4);
        root.right.left.left.left = new TreeNode(2);
        root.right.left.left.right = new TreeNode(5);
        root.right.left.right = new TreeNode(14);
        root.right.left.right.left = new TreeNode(11);
        root.right.left.right.right = new TreeNode(15);

//        root.right.right = new TreeNode(13);
//        root.right.right.left = new TreeNode(20);
//        root.right.right.right = new TreeNode(16);

        int num = findMaxSearchTree(root);

        System.out.println(num);
    }

}
